<HTML>
<HEAD>
<TITLE>Utilities (Subsystem of AIMA Code)</TITLE> 
<!-- Changed by: Peter Norvig, 30-Oct-1996 -->
</HEAD> 
<BODY bgcolor="#ffffff"> 

<H1>Utilities (Subsystem of AIMA Code)</H1>

The <b>utilities</b> system provides a set of basic functions, macros,
and data types that are used throughout the other systems.  For
example, we define the <tt>while</tt> and <tt>for</tt> iteration
macros, the two-dimensional point (and operations on it), the queue
and binary tree types, and some debugging and testing code.

<P><HR size=3></UL><A HREF="../utilities/"><B>utilities/</B></A>:
<UL> <LI><A HREF="#utilities/utilities.lisp"><B>utilities.lisp</B></A>  Basic utility functions and macros, used throughout the code. <LI><A HREF="#utilities/binary-tree.lisp"><B>binary-tree.lisp</B></A>   The following definitions implement binary search trees.<LI><A HREF="#utilities/queue.lisp"><B>queue.lisp</B></A>  The Queue datatype<LI><A HREF="#utilities/cltl2.lisp"><B>cltl2.lisp</B></A>  Compatibility package for 'Common Lisp the Language: 2nd edition'<LI><A HREF="#utilities/test-utilities.lisp"><B>test-utilities.lisp</B></A>  Test cases for the basic utilities</UL>

<A NAME="utilities/utilities.lisp"><HR>
<H2>File <A HREF="../utilities/utilities.lisp">utilities/utilities.lisp</A></H2></A>
<H2><I> Basic utility functions and macros, used throughout the code. </I>
</H2>
<I> The utilities are divided into control flow macros, list</I>
<I> utilities, functions for 2-dimensional points, numeric utilities,</I>
<I> some trivial functions, utilities for strings, symbols and</I>
<I> printing, a debugging tool, and a testing tool."</I>
<H2><I> Control Flow Macros</I>
</H2>
<I> We define iteration macros to match the book's pseudo-code.</I>
<I> This could all be done with LOOP, but some users don't have</I>
<I> the LOOP from the 2nd edition of 'Common Lisp: the Language'.</I>
<A NAME="while"><P><A HREF="../utilities/utilities.lisp"><B>while</B></A></A> <I>macro</I> (test
                                                                                            do
                                                                                            &body
                                                                                            body)
  <blockquote>Execute body while the test is true.</blockquote>
<A NAME="for-each"><P><A HREF="../utilities/utilities.lisp"><B>for-each</B></A></A> <I>macro</I> (var
                                                                                                  in
                                                                                                  list
                                                                                                  do
                                                                                                  &body
                                                                                                  body)
  <blockquote>Execute body for each element of list.  VAR can be a list or tree
  of variables, in which case the elements are destructured.</blockquote>
<A NAME="for"><P><A HREF="../utilities/utilities.lisp"><B>for</B></A></A> <I>macro</I> (var
                                                                                        =
                                                                                        start
                                                                                        to
                                                                                        end
                                                                                        do
                                                                                        &body
                                                                                        body)
  <blockquote>Execute body with var bound to succesive integers.</blockquote>
<A NAME="deletef"><P><A HREF="../utilities/utilities.lisp"><B>deletef</B></A></A> <I>macro</I> (item
                                                                                                sequence
                                                                                                &rest
                                                                                                keys
                                                                                                &environment
                                                                                                env)
  <blockquote>Destructively delete item from sequence, which must be SETF-able.</blockquote>
<A NAME="define-if-undefined"><P><A HREF="../utilities/utilities.lisp"><B>define-if-undefined</B></A></A> <I>macro</I> (&rest
                                                                                                                        definitions)
  <blockquote>Use this to conditionally define functions, variables, or macros that
  may or may not be pre-defined in this Lisp.  This can be used to provide
  CLtL2 compatibility for older Lisps.</blockquote>
<H2><I> List Utilities</I>
</H2>
<A NAME="length>1"><P><A HREF="../utilities/utilities.lisp"><B>length>1</B></A></A> <I>function</I> (list)
  <blockquote>Is this a list of 2 or more elements?</blockquote>
<A NAME="length=1"><P><A HREF="../utilities/utilities.lisp"><B>length=1</B></A></A> <I>function</I> (list)
  <blockquote>Is this a list of exactly one element?</blockquote>
<A NAME="random-element"><P><A HREF="../utilities/utilities.lisp"><B>random-element</B></A></A> <I>function</I> (list)
  <blockquote>Return some element of the list, chosen at random.</blockquote>
<A NAME="mappend"><P><A HREF="../utilities/utilities.lisp"><B>mappend</B></A></A> <I>function</I> (fn
                                                                                                   &rest
                                                                                                   lists)
  <blockquote>Apply fn to respective elements of list(s), and append results.</blockquote>
<A NAME="starts-with"><P><A HREF="../utilities/utilities.lisp"><B>starts-with</B></A></A> <I>function</I> (list
                                                                                                           element)
  <blockquote>Is this a list that starts with the given element?</blockquote>
<A NAME="last1"><P><A HREF="../utilities/utilities.lisp"><B>last1</B></A></A> <I>function</I> (list)
  <blockquote>Return the last element of a list.</blockquote>
<A NAME="left-rotate"><P><A HREF="../utilities/utilities.lisp"><B>left-rotate</B></A></A> <I>function</I> (list)
  <blockquote>Move the first element to the end of the list.</blockquote>
<A NAME="right-rotate"><P><A HREF="../utilities/utilities.lisp"><B>right-rotate</B></A></A> <I>function</I> (list)
  <blockquote>Move the last element to the front of the list.</blockquote>
<A NAME="transpose"><P><A HREF="../utilities/utilities.lisp"><B>transpose</B></A></A> <I>function</I> (list-of-lists)
  <blockquote>Transpose a matrix represented as a list of lists.
  Example: (transpose '((a b c) (d e f))) => ((a d) (b e) (c f)).</blockquote>
<A NAME="reuse-cons"><P><A HREF="../utilities/utilities.lisp"><B>reuse-cons</B></A></A> <I>function</I> (x
                                                                                                         y
                                                                                                         x-y)
  <blockquote>Return (cons x y), or reuse x-y if it is equal to (cons x y)</blockquote>
<A NAME="make-exp"><P><A HREF="../utilities/utilities.lisp"><B>make-exp</B></A></A> <I>function</I> (op
                                                                                                     &rest
                                                                                                     args)
  <P>
<A NAME="op"><P><A HREF="../utilities/utilities.lisp"><B>op</B></A></A> <I>function</I> (exp)
  <blockquote>Operator of an expression</blockquote>
<A NAME="args"><P><A HREF="../utilities/utilities.lisp"><B>args</B></A></A> <I>function</I> (exp)
  <blockquote>Arguments of an expression</blockquote>
<A NAME="arg1"><P><A HREF="../utilities/utilities.lisp"><B>arg1</B></A></A> <I>function</I> (exp)
  <blockquote>First argument</blockquote>
<A NAME="arg2"><P><A HREF="../utilities/utilities.lisp"><B>arg2</B></A></A> <I>function</I> (exp)
  <blockquote>Second argument</blockquote>
<A NAME="prefix->infix"><P><A HREF="../utilities/utilities.lisp"><B>prefix->infix</B></A></A> <I>function</I> (exp)
  <blockquote>Convert a fully parenthesized prefix expression into infix notation.</blockquote>
<A NAME="insert-between"><P><A HREF="../utilities/utilities.lisp"><B>insert-between</B></A></A> <I>function</I> (item
                                                                                                                 list)
  <blockquote>Insert item between every element of list.</blockquote>
<H2><I> Functions for manipulating 2-dimensional points </I>
</H2>
<A NAME="xy"><P><A HREF="../utilities/utilities.lisp"><B>xy</B></A></A> <I>type</I> (x
                                                                                     y)
  <blockquote>A two-dimensional (i.e. x and y) point.</blockquote>
<A NAME="xy-p"><P><A HREF="../utilities/utilities.lisp"><B>xy-p</B></A></A> <I>function</I> (arg)
  <blockquote>Is the argument a 2-D point?</blockquote>
<A NAME="@"><P><A HREF="../utilities/utilities.lisp"><B>@</B></A></A> <I>function</I> (x
                                                                                       y)
  <blockquote>Create a 2-D point</blockquote>
<A NAME="xy-equal"><P><A HREF="../utilities/utilities.lisp"><B>xy-equal</B></A></A> <I>function</I> (p
                                                                                                     q)
  <P>
<A NAME="xy-add"><P><A HREF="../utilities/utilities.lisp"><B>xy-add</B></A></A> <I>function</I> (p
                                                                                                 q)
  <blockquote>Add two points, component-wise.</blockquote>
<A NAME="xy-distance"><P><A HREF="../utilities/utilities.lisp"><B>xy-distance</B></A></A> <I>function</I> (p
                                                                                                           q)
  <blockquote>The distance between two points.</blockquote>
<A NAME="x+y-distance"><P><A HREF="../utilities/utilities.lisp"><B>x+y-distance</B></A></A> <I>function</I> (p
                                                                                                             q)
  <blockquote>The 'city block distance' between two points.</blockquote>
<A NAME="xy-between"><P><A HREF="../utilities/utilities.lisp"><B>xy-between</B></A></A> <I>function</I> (xy1
                                                                                                         xy2
                                                                                                         xy3)
  <blockquote>Predicate; return t iff xy1 is between xy2 and xy3. Points are collinear.</blockquote>
<A NAME="rotate"><P><A HREF="../utilities/utilities.lisp"><B>rotate</B></A></A> <I>function</I> (o
                                                                                                 a
                                                                                                 b
                                                                                                 c
                                                                                                 d)
  <P>
<A NAME="inside"><P><A HREF="../utilities/utilities.lisp"><B>inside</B></A></A> <I>function</I> (l
                                                                                                 xmax
                                                                                                 ymax)
  <blockquote>Is the point l inside a rectangle from 0,0 to xmax,ymax?</blockquote>
<H2><I> Numeric Utilities</I>
</H2>
<A NAME="infinity"><P><A HREF="../utilities/utilities.lisp"><B>infinity</B></A></A> <I>constant</I> 
  <P>
<A NAME="minus-infinity"><P><A HREF="../utilities/utilities.lisp"><B>minus-infinity</B></A></A> <I>constant</I> 
  <P>
<A NAME="average"><P><A HREF="../utilities/utilities.lisp"><B>average</B></A></A> <I>function</I> (numbers)
  <blockquote>Numerical average (mean) of a list of numbers.</blockquote>
<A NAME="running-average"><P><A HREF="../utilities/utilities.lisp"><B>running-average</B></A></A> <I>function</I> (avg
                                                                                                                   new
                                                                                                                   n)
  <blockquote>Calculate new average given previous average over n data points</blockquote>
<A NAME="square"><P><A HREF="../utilities/utilities.lisp"><B>square</B></A></A> <I>function</I> (x)
  <P>
<A NAME="sum"><P><A HREF="../utilities/utilities.lisp"><B>sum</B></A></A> <I>function</I> (numbers
                                                                                           &optional
                                                                                           key)
  <blockquote>Add up all the numbers; if KEY is given, apply it to each number first.</blockquote>
<A NAME="between"><P><A HREF="../utilities/utilities.lisp"><B>between</B></A></A> <I>function</I> (x
                                                                                                   y
                                                                                                   z)
  <blockquote>Predicate; return t iff number x is between numbers y and z.</blockquote>
<A NAME="rms-error"><P><A HREF="../utilities/utilities.lisp"><B>rms-error</B></A></A> <I>function</I> (predicted
                                                                                                       target)
  <blockquote>Compute root mean square error between predicted list and target list</blockquote>
<A NAME="ms-error"><P><A HREF="../utilities/utilities.lisp"><B>ms-error</B></A></A> <I>function</I> (predicted
                                                                                                     target)
  <blockquote>Compute mean square error between predicted list and target list</blockquote>
<A NAME="boolean-error"><P><A HREF="../utilities/utilities.lisp"><B>boolean-error</B></A></A> <I>function</I> (predicted
                                                                                                               target)
  <P>
<A NAME="dot-product"><P><A HREF="../utilities/utilities.lisp"><B>dot-product</B></A></A> <I>function</I> (l1
                                                                                                           l2)
  <P>
<A NAME="iota"><P><A HREF="../utilities/utilities.lisp"><B>iota</B></A></A> <I>function</I> (n
                                                                                             &optional
                                                                                             start-at)
  <blockquote>Return a list of n consecutive integers, by default starting at 0.</blockquote>
<A NAME="random-integer"><P><A HREF="../utilities/utilities.lisp"><B>random-integer</B></A></A> <I>function</I> (from
                                                                                                                 to)
  <blockquote>Return an integer chosen at random from the given interval.</blockquote>
<A NAME="normal"><P><A HREF="../utilities/utilities.lisp"><B>normal</B></A></A> <I>function</I> (x
                                                                                                 mu
                                                                                                 sigma)
  <P>
<A NAME="sample-with-replacement"><P><A HREF="../utilities/utilities.lisp"><B>sample-with-replacement</B></A></A> <I>function</I> (n
                                                                                                                                   population)
  <P>
<A NAME="sample-without-replacement"><P><A HREF="../utilities/utilities.lisp"><B>sample-without-replacement</B></A></A> <I>function</I> (n
                                                                                                                                         population
                                                                                                                                         &optional
                                                                                                                                         m)
  <P>
<A NAME="fuzz"><P><A HREF="../utilities/utilities.lisp"><B>fuzz</B></A></A> <I>function</I> (quantity
                                                                                             &optional
                                                                                             proportion
                                                                                             round-off)
  <blockquote>Add and also subtract a random fuzz-factor to a quantity.</blockquote>
<A NAME="round-off"><P><A HREF="../utilities/utilities.lisp"><B>round-off</B></A></A> <I>function</I> (number
                                                                                                       precision)
  <blockquote>Round off the number to specified precision. E.g. (round-off 1.23 .1) = 1.2</blockquote>
<H2><I> Trivial Functions</I>
</H2>
<A NAME="nothing"><P><A HREF="../utilities/utilities.lisp"><B>nothing</B></A></A> <I>function</I> (&rest
                                                                                                   args)
  <blockquote>Don't do anything, and return nil.</blockquote>
<A NAME="declare-ignore"><P><A HREF="../utilities/utilities.lisp"><B>declare-ignore</B></A></A> <I>function</I> (&rest
                                                                                                                 args)
  <blockquote>Ignore the arguments.</blockquote>
<A NAME="true"><P><A HREF="../utilities/utilities.lisp"><B>true</B></A></A> <I>function</I> (&rest
                                                                                             args)
  <blockquote>Always return true.</blockquote>
<A NAME="false"><P><A HREF="../utilities/utilities.lisp"><B>false</B></A></A> <I>function</I> (&rest
                                                                                               args)
  <blockquote>Always return false.</blockquote>
<A NAME="required"><P><A HREF="../utilities/utilities.lisp"><B>required</B></A></A> <I>function</I> (&optional
                                                                                                     msg
                                                                                                     &rest
                                                                                                     args)
  <blockquote>If this ever gets called, it means something that was required was not
  supplied.  Use as default value for &key args or defstruct slots.</blockquote>
<H2><I> Utilities for strings and symbols and printing</I>
</H2>
<A NAME="stringify"><P><A HREF="../utilities/utilities.lisp"><B>stringify</B></A></A> <I>function</I> (exp)
  <blockquote>Coerce argument to a string.</blockquote>
<A NAME="concat-symbol"><P><A HREF="../utilities/utilities.lisp"><B>concat-symbol</B></A></A> <I>function</I> (&rest
                                                                                                               args)
  <blockquote>Concatenate the args into one string, and turn that into a symbol.</blockquote>
<A NAME="print-grid"><P><A HREF="../utilities/utilities.lisp"><B>print-grid</B></A></A> <I>function</I> (array
                                                                                                         &key
                                                                                                         stream
                                                                                                         key
                                                                                                         width)
  <blockquote>Print the contents of a 2-D array, numbering the edges.</blockquote>
<A NAME="print-centered"><P><A HREF="../utilities/utilities.lisp"><B>print-centered</B></A></A> <I>function</I> (string
                                                                                                                 width
                                                                                                                 &optional
                                                                                                                 stream)
  <blockquote>Print STRING centered in a field WIDTH wide.</blockquote>
<A NAME="print-repeated"><P><A HREF="../utilities/utilities.lisp"><B>print-repeated</B></A></A> <I>function</I> (string
                                                                                                                 n
                                                                                                                 &optional
                                                                                                                 stream)
  <blockquote>Print the string n times.</blockquote>
<A NAME="print-dashes"><P><A HREF="../utilities/utilities.lisp"><B>print-dashes</B></A></A> <I>function</I> (width
                                                                                                             &optional
                                                                                                             stream
                                                                                                             separate-line)
  <blockquote>Print a line of dashes WIDTH wide.</blockquote>
<H2><I> Assorted conversion utilities and predicates</I>
</H2>
<A NAME="copy-array"><P><A HREF="../utilities/utilities.lisp"><B>copy-array</B></A></A> <I>function</I> (a)
  <blockquote>Make a copy of an array.</blockquote>
<A NAME="copy-subarray"><P><A HREF="../utilities/utilities.lisp"><B>copy-subarray</B></A></A> <I>function</I> (a
                                                                                                               b
                                                                                                               indices
                                                                                                               dim)
  <P>
<A NAME="array->vector"><P><A HREF="../utilities/utilities.lisp"><B>array->vector</B></A></A> <I>function</I> (array)
  <blockquote>Convert a multi-dimensional array to a vector with the same elements.</blockquote>
<A NAME="plot-alist"><P><A HREF="../utilities/utilities.lisp"><B>plot-alist</B></A></A> <I>function</I> (alist
                                                                                                         file)
  <P>
<A NAME="copy-hash-table"><P><A HREF="../utilities/utilities.lisp"><B>copy-hash-table</B></A></A> <I>function</I> (h1
                                                                                                                   &optional
                                                                                                                   copy-fn)
  <P>
<A NAME="hash-table->list"><P><A HREF="../utilities/utilities.lisp"><B>hash-table->list</B></A></A> <I>function</I> (table)
  <blockquote>Convert a hash table into a list of (key . val) pairs.</blockquote>
<A NAME="hprint"><P><A HREF="../utilities/utilities.lisp"><B>hprint</B></A></A> <I>function</I> (h
                                                                                                 &optional
                                                                                                 stream)
  <blockquote>prints a hash table line by line</blockquote>
<A NAME="compose"><P><A HREF="../utilities/utilities.lisp"><B>compose</B></A></A> <I>function</I> (f
                                                                                                   g)
  <blockquote>Return a function h such that (h x) = (f (g x)).</blockquote>
<A NAME="the-biggest"><P><A HREF="../utilities/utilities.lisp"><B>the-biggest</B></A></A> <I>function</I> (fn
                                                                                                           l)
  <P>
<A NAME="the-biggest-random-tie"><P><A HREF="../utilities/utilities.lisp"><B>the-biggest-random-tie</B></A></A> <I>function</I> (fn
                                                                                                                                 l)
  <P>
<A NAME="the-biggest-that"><P><A HREF="../utilities/utilities.lisp"><B>the-biggest-that</B></A></A> <I>function</I> (fn
                                                                                                                     p
                                                                                                                     l)
  <P>
<A NAME="the-smallest"><P><A HREF="../utilities/utilities.lisp"><B>the-smallest</B></A></A> <I>function</I> (fn
                                                                                                             l)
  <P>
<A NAME="the-smallest-random-tie"><P><A HREF="../utilities/utilities.lisp"><B>the-smallest-random-tie</B></A></A> <I>function</I> (fn
                                                                                                                                   l)
  <P>
<A NAME="the-smallest-that"><P><A HREF="../utilities/utilities.lisp"><B>the-smallest-that</B></A></A> <I>function</I> (fn
                                                                                                                       p
                                                                                                                       l)
  <P>
<H2><I> Debugging tool</I>
</H2>
<A NAME="*debugging*"><P><A HREF="../utilities/utilities.lisp"><B>*debugging*</B></A></A> <I>variable</I> 
  <P>
<A NAME="dprint"><P><A HREF="../utilities/utilities.lisp"><B>dprint</B></A></A> <I>function</I> (&rest
                                                                                                 args)
  <blockquote>Echo all the args when *debugging* is true.  Return the first one.</blockquote>
<H2><I> Testing Tool: deftest and test</I>
</H2>
<A NAME="deftest"><P><A HREF="../utilities/utilities.lisp"><B>deftest</B></A></A> <I>macro</I> (name
                                                                                                &rest
                                                                                                examples)
  <blockquote>Define a set of test examples.  Each example is of the form (exp test)
  or (exp).  Evaluate exp and see if the result passes the test. Within the
  test, the result is bound to *.  The example ((f 2))) has no test to
  fail, so it alweays passes the test.  But ((+ 2 2) (= * 3)) has the test
  (= * 3), which fails because * will be bound to the result 4, so the test
  fails.  Call (TEST name) to count how many tests are failed within the
  named test.  NAME is the name of an aima-system.</blockquote>
<A NAME="add-test"><P><A HREF="../utilities/utilities.lisp"><B>add-test</B></A></A> <I>function</I> (name
                                                                                                     examples)
  <blockquote>The functional interface for deftest: adds test examples to a system.</blockquote>
<A NAME="test"><P><A HREF="../utilities/utilities.lisp"><B>test</B></A></A> <I>function</I> (&optional
                                                                                             name
                                                                                             print?)
  <blockquote>Run a test suite and sum the number of errors.  If all is well, this
  should return 0.  The second argument says what to print: nil for
  nothing, t for everything, or FAIL for just those examples that fail.
  If there are no test examples in the named system, put the system has
  other systems as parts, run the tests for all those and sum the result.</blockquote>
<A NAME="test-example"><P><A HREF="../utilities/utilities.lisp"><B>test-example</B></A></A> <I>function</I> (example
                                                                                                             &optional
                                                                                                             print?)
  <blockquote>Does the EXP part of this example pass the TEST?</blockquote>
<A NAME="utilities/binary-tree.lisp"><HR>
<H2>File <A HREF="../utilities/binary-tree.lisp">utilities/binary-tree.lisp</A></H2></A>
<H2><I>  The following definitions implement binary search trees.</I>
</H2>
<I>  They are not balanced as yet.  Currently, they all order their</I>
<I>  elements by #'<, and test for identity of elements by #'eq.</I>
<A NAME="search-tree-node"><P><A HREF="../utilities/binary-tree.lisp"><B>search-tree-node</B></A></A> <I>type</I> (value
                                                                                                                   num-elements
                                                                                                                   key
                                                                                                                   parent
                                                                                                                   leftson
                                                                                                                   rightson)
  <blockquote>node for binary search tree</blockquote>
<A NAME="make-search-tree"><P><A HREF="../utilities/binary-tree.lisp"><B>make-search-tree</B></A></A> <I>function</I> (root-elem
                                                                                                                       root-key)
  <blockquote>return dummy header for binary search tree, with initial
  element root-elem whose key is root-key.</blockquote>
<A NAME="create-sorted-tree"><P><A HREF="../utilities/binary-tree.lisp"><B>create-sorted-tree</B></A></A> <I>function</I> (list-of-elems
                                                                                                                           key-fun)
  <blockquote>return binary search tree containing list-of-elems ordered according
  tp key-fun</blockquote>
<A NAME="empty-tree"><P><A HREF="../utilities/binary-tree.lisp"><B>empty-tree</B></A></A> <I>function</I> (root)
  <blockquote>Predicate of search trees; return t iff empty.</blockquote>
<A NAME="leftmost"><P><A HREF="../utilities/binary-tree.lisp"><B>leftmost</B></A></A> <I>function</I> (tree-node)
  <blockquote>return leftmost descendant of tree-node</blockquote>
<A NAME="rightmost"><P><A HREF="../utilities/binary-tree.lisp"><B>rightmost</B></A></A> <I>function</I> (header)
  <blockquote>return rightmost descendant of header</blockquote>
<A NAME="pop-least-element"><P><A HREF="../utilities/binary-tree.lisp"><B>pop-least-element</B></A></A> <I>function</I> (header)
  <blockquote>return least element of binary search tree; delete from tree as side-effect</blockquote>
<A NAME="pop-largest-element"><P><A HREF="../utilities/binary-tree.lisp"><B>pop-largest-element</B></A></A> <I>function</I> (header)
  <blockquote>return largest element of binary search tree; delete from tree as side-effect</blockquote>
<A NAME="least-key"><P><A HREF="../utilities/binary-tree.lisp"><B>least-key</B></A></A> <I>function</I> (header)
  <blockquote>return least key of binary search tree; no side effects</blockquote>
<A NAME="largest-key"><P><A HREF="../utilities/binary-tree.lisp"><B>largest-key</B></A></A> <I>function</I> (header)
  <blockquote>return least key of binary search tree; no side effects</blockquote>
<A NAME="insert-element"><P><A HREF="../utilities/binary-tree.lisp"><B>insert-element</B></A></A> <I>function</I> (element
                                                                                                                   parent
                                                                                                                   key
                                                                                                                   &optional
                                                                                                                   direction)
  <blockquote>insert new element at proper place in binary search tree</blockquote>
<A NAME="randomized-insert-element"><P><A HREF="../utilities/binary-tree.lisp"><B>randomized-insert-element</B></A></A> <I>function</I> (element
                                                                                                                                         parent
                                                                                                                                         key
                                                                                                                                         &optional
                                                                                                                                         direction)
  <blockquote>insert new element at proper place in binary search tree -- break
   ties randomly</blockquote>
<A NAME="randomized-push"><P><A HREF="../utilities/binary-tree.lisp"><B>randomized-push</B></A></A> <I>function</I> (element
                                                                                                                     list)
  <blockquote>return list with element destructively inserted at random into list</blockquote>
<A NAME="find-element"><P><A HREF="../utilities/binary-tree.lisp"><B>find-element</B></A></A> <I>function</I> (element
                                                                                                               parent
                                                                                                               key
                                                                                                               &optional
                                                                                                               direction)
  <blockquote>return t if element is int tree</blockquote>
<A NAME="delete-element"><P><A HREF="../utilities/binary-tree.lisp"><B>delete-element</B></A></A> <I>function</I> (element
                                                                                                                   parent
                                                                                                                   key
                                                                                                                   &optional
                                                                                                                   error-p)
  <blockquote>delete element from binary search tree</blockquote>
<A NAME="inorder-successor"><P><A HREF="../utilities/binary-tree.lisp"><B>inorder-successor</B></A></A> <I>function</I> (tree-node)
  <blockquote>return inorder-successor of tree-node assuming it has a right son</blockquote>
<A NAME="list-elements"><P><A HREF="../utilities/binary-tree.lisp"><B>list-elements</B></A></A> <I>function</I> (parent)
  <blockquote>return list of elements in tree</blockquote>
<A NAME="utilities/queue.lisp"><HR>
<H2>File <A HREF="../utilities/queue.lisp">utilities/queue.lisp</A></H2></A>
<H2><I> The Queue datatype</I>
</H2>
<I> We can remove elements form the front of a queue.  We can add elements in</I>
<I> three ways: to the front, to the back, or ordered by some numeric score.</I>
<I> This is done with the following enqueing functions, which make use of the</I>
<I> following implementations of the elements:</I>
<I>   ENQUEUE-AT-FRONT - elements are a list</I>
<I>   ENQUEUE-AT-END   - elements are a list, with a pointer to end</I>
<I>   ENQUEUE-BY-PRIORITY - elements are a heap, implemented as an array</I>
<I> The best element in the queue is always in position 0.</I>
<I> The heap implementation is taken from "Introduction to Algorithms" by</I>
<I> Cormen, Lieserson & Rivest [CL&R], Chapter 7.  We could certainly speed</I>
<I> up the constant factors of this implementation.  It is meant to be clear</I>
<I> and simple and O(log n), but not super efficient.  Consider a Fibonacci</I>
<I> heap [Page 420 CL&R] if you really have large queues to deal with.</I>
<A NAME="q"><P><A HREF="../utilities/queue.lisp"><B>q</B></A></A> <I>type</I> (key
                                                                               last
                                                                               elements)
  <P>
<H2><I> Basic Operations on Queues</I>
</H2>
<A NAME="make-empty-queue"><P><A HREF="../utilities/queue.lisp"><B>make-empty-queue</B></A></A> <I>function</I> ()
  <P>
<A NAME="empty-queue?"><P><A HREF="../utilities/queue.lisp"><B>empty-queue?</B></A></A> <I>function</I> (q)
  <blockquote>Are there no elements in the queue?</blockquote>
<A NAME="queue-front"><P><A HREF="../utilities/queue.lisp"><B>queue-front</B></A></A> <I>function</I> (q)
  <blockquote>Return the element at the front of the queue.</blockquote>
<A NAME="remove-front"><P><A HREF="../utilities/queue.lisp"><B>remove-front</B></A></A> <I>function</I> (q)
  <blockquote>Remove the element from the front of the queue and return it.</blockquote>
<H2><I> The Three Enqueing Functions</I>
</H2>
<A NAME="enqueue-at-front"><P><A HREF="../utilities/queue.lisp"><B>enqueue-at-front</B></A></A> <I>function</I> (q
                                                                                                                 items)
  <blockquote>Add a list of items to the front of the queue.</blockquote>
<A NAME="enqueue-at-end"><P><A HREF="../utilities/queue.lisp"><B>enqueue-at-end</B></A></A> <I>function</I> (q
                                                                                                             items)
  <blockquote>Add a list of items to the end of the queue.</blockquote>
<A NAME="enqueue-by-priority"><P><A HREF="../utilities/queue.lisp"><B>enqueue-by-priority</B></A></A> <I>function</I> (q
                                                                                                                       items
                                                                                                                       key)
  <blockquote>Insert the items by priority according to the key function.</blockquote>
<H2><I> The Heap Implementation of Priority Queues</I>
</H2>
<I> The idea is to store a heap in an array so that the heap property is</I>
<I> maintained for all elements: heap[Parent(i)] <= heap[i].  Note that we</I>
<I> start at index 0, not 1, and that we put the lowest value at the top of</I>
<I> the heap, not the highest value.</I>
<A NAME="heap-val"><P><A HREF="../utilities/queue.lisp"><B>heap-val</B></A></A> <I>function</I> (heap
                                                                                                 i
                                                                                                 key)
  <P>
<A NAME="heap-parent"><P><A HREF="../utilities/queue.lisp"><B>heap-parent</B></A></A> <I>function</I> (i)
  <P>
<A NAME="heap-left"><P><A HREF="../utilities/queue.lisp"><B>heap-left</B></A></A> <I>function</I> (i)
  <P>
<A NAME="heap-right"><P><A HREF="../utilities/queue.lisp"><B>heap-right</B></A></A> <I>function</I> (i)
  <P>
<A NAME="heapify"><P><A HREF="../utilities/queue.lisp"><B>heapify</B></A></A> <I>function</I> (heap
                                                                                               i
                                                                                               key)
  <blockquote>Assume that the children of i are heaps, but that heap[i] may be 
  larger than its children.  If it is, move heap[i] down where it belongs.
  [Page 143 CL&R].</blockquote>
<A NAME="heap-extract-min"><P><A HREF="../utilities/queue.lisp"><B>heap-extract-min</B></A></A> <I>function</I> (heap
                                                                                                                 key)
  <blockquote>Pop the best (lowest valued) item off the heap. [Page 150 CL&R].</blockquote>
<A NAME="heap-insert"><P><A HREF="../utilities/queue.lisp"><B>heap-insert</B></A></A> <I>function</I> (heap
                                                                                                       item
                                                                                                       key)
  <blockquote>Put an item into a heap. [Page 150 CL&R].</blockquote>
<A NAME="make-heap"><P><A HREF="../utilities/queue.lisp"><B>make-heap</B></A></A> <I>function</I> (&optional
                                                                                                   size)
  <P>
<A NAME="heap-sort"><P><A HREF="../utilities/queue.lisp"><B>heap-sort</B></A></A> <I>function</I> (numbers
                                                                                                   &key
                                                                                                   key)
  <blockquote>Return a sorted list, with elements that are < according to key first.</blockquote>
<A NAME="utilities/cltl2.lisp"><HR>
<H2>File <A HREF="../utilities/cltl2.lisp">utilities/cltl2.lisp</A></H2></A>
<H2><I> Compatibility package for 'Common Lisp the Language: 2nd edition'</I>
</H2>
<I> Functions and macros in CLtL2 that are not in the first edition of</I>
<I> the book, and thus not in some old implementations of Common Lisp.</I>
<A NAME="with-simple-restart"><P><A HREF="../utilities/cltl2.lisp"><B>with-simple-restart</B></A></A> <I>macro</I> (restart
                                                                                                                    &rest
                                                                                                                    body)
  <blockquote>Like PROGN, except provides control over restarts if there is an error.</blockquote>
<A NAME="destructuring-bind"><P><A HREF="../utilities/cltl2.lisp"><B>destructuring-bind</B></A></A> <I>macro</I> (lambda-list
                                                                                                                  list
                                                                                                                  &body
                                                                                                                  body)
  <blockquote>Bind the variables in lambda-list to the result list and execute body.</blockquote>
<H2><I> Mini Implementation of CLOS</I>
</H2>
<I> If you don't have CLOS (the Common Lisp Object System) installed,</I>
<I> then this defines a simple version of DEFMETHOD which only</I>
<I> dispatches on the first argument, and works for structures (and</I>
<I> some other types) but not classes.  Note that you can still do</I>
<I> (single) inheritance with structures using the :include option.</I>
<I> To properly inform DEFMETHOD of the inheritance tree, you should</I>
<I> use DEFSTRUCTURE rather than DEFSTRUCT.  This has the added</I>
<I> benefit of allowing you to write PRINT-STRUCTURE methods rather</I>
<I> than :print-function functions, if you like (they will be</I>
<I> inherited properly, and they don't have the silly DEPTH argument).</I>
<A NAME="defstructure"><P><A HREF="../utilities/cltl2.lisp"><B>defstructure</B></A></A> <I>macro</I> (type-and-args
                                                                                                      &rest
                                                                                                      slots)
  <blockquote>This is just like DEFSTRUCT, except it keeps track of :include types, for
  the benefit of METHOD-FOR, and it makes printing go through PRINT-STRUCTURE.</blockquote>
<A NAME="print-structure:t"><P><A HREF="../utilities/cltl2.lisp"><B>print-structure</B></A></A> <I>method</I> ((structure
                                                                                                                t)
                                                                                                               stream)
  <blockquote>Print a structure.  You can specialize this function.
  It will be called to print anything defined with DEFSTRUCTURE.</blockquote>
<A NAME="defmethod"><P><A HREF="../utilities/cltl2.lisp"><B>defmethod</B></A></A> <I>macro</I> (name
                                                                                                ((var
                                                                                                  class)
                                                                                                 &rest
                                                                                                 other-args)
                                                                                                &rest
                                                                                                body)
  <blockquote>This version of DEFMETHOD is like the CLOS version, except it only
  dispatches on the first argument, and it only handles structures and
  some built-in types, not classes.</blockquote>
<A NAME="ensure-generic-function"><P><A HREF="../utilities/cltl2.lisp"><B>ensure-generic-function</B></A></A> <I>function</I> (name)
  <blockquote>Define NAME to be a generic function.</blockquote>
<A NAME="supertype"><P><A HREF="../utilities/cltl2.lisp"><B>supertype</B></A></A> <I>function</I> (type)
  <blockquote>Find the most specific supertype of this type.</blockquote>
<A NAME="call-method-for"><P><A HREF="../utilities/cltl2.lisp"><B>call-method-for</B></A></A> <I>function</I> (name
                                                                                                               type
                                                                                                               var
                                                                                                               args)
  <blockquote>Find the method for this type, following :supertype links if needed.</blockquote>
<A NAME="utilities/test-utilities.lisp"><HR>
<H2>File <A HREF="../utilities/test-utilities.lisp">utilities/test-utilities.lisp</A></H2></A>
<H2><I> Test cases for the basic utilities</I>
</H2>
<HR>
<TABLE BORDER=4 CELLPADDING=4 CELLSPACING=0><tr>
<td> <A HREF="../../aima.html">AIMA Home</A>
<td> <A HREF="../../contact.html">Authors</A>
<td> <A HREF="overview.html">Lisp Code</A>
<td> <A HREF="../../prog.html">AI Programming</A>
<td> <A HREF="../../instructors.html">Instructors Pages</A>
</TABLE>
</BODY> 
</HTML>
